7565. Простой набор задач

Самое сложное на любом ACM ICPC соревновании – создать набор задач с разумным количеством простых задач. На соревновании Not Easy European Regional Contest эта задача решается так.

Имеется n членов жюри (судей). Они пронумерованы от 1 до n. Судья номер i приготовил p_i простых задач перед встречей жюри. Каждая задача имеет сложность от 0 до 49 (чем больше тем тяжелее). Каждый судья также знает большое (например бесконечное) количество трудных задач (их сложность равна 50). Для соревнования во время встречи жюри следует выбрать k задач.

Они начинают предлагать задачи в порядке возрастания номеров судей. Первый судья предлагает первую задачу со своего списка оставшихся легких задач (или трудных, если все свои легкие он уже предложил). Предлагаемая задача будет выбрана на соревнование, если ее сложность больше или равна общей сложности уже выбранных задач, иначе она считается слишком легкой. Затем второй судья делает то же самое и т.д.; после n - го судьи свои задачи снова предлагает первый, и так далее. Описанная процедура прекращается, как только будет выбрано k задач.

Если все судьи предложили все свои легкие задачи, но при этом они до сих пор выбрали менее k задач, то они начинают вносить в список соревнования тяжелые задачи чтобы завершить его составление.

Вам следует вычислить сложность набора задач, составленного жюри.

Вход. Первая строка содержит количество судей n (2 ≤ n ≤ 10) и количество задач k (8 ≤ k ≤ 14). i-ая из следующих n строк содержит описание задач, подготовленных i-ым судьей. Она начинается значением p_i (1 ≤ p_i ≤ 10), за которым следует p_i неотрицательных целых чисел между 0 и 49 – сложности задач, приготовленных i-ым судьей в том же порядке, в котором он будет их предлагать.

Выход. Вывести одно число – общую сложность всех выбранных задач.

Пример входа 1	Пример выхода 1
3 8 5 0 3 12 1 10 4 1 1 23 20 4 1 5 17 49	94
Пример входа 2	Пример выхода 2
3 10 2 1 3 1 1 2 2 5	354

Объяснение

В первом примере сначала будут выбраны три задачи со сложностями 0, 1 и 1. Далее первый судья предложит задачу со сложностью 3 и она будет выбрана. Задача второго судьи со сложностью 1 будет отклонена, так она будет считаться слишком простой. Следующие задачи, предложенные третьим, первым и вторым судьями, будут выбраны (их сложности равны соответственно 5, 12 и 23). Следующие три задачи со сложностями 17, 1 и 20 будут отклонены, и набор будет завершен задачей со сложностью 49. Так что общая сложность набора задач составит 94.

Во втором примере сначала будут выбраны три задачи со сложностями 1, 1 и 2. Вторая задача первого судьи (со сложностью 3) слишком проста. У второго судьи закончились простые задачи, поэтому он предлагает задачу со сложностью 50, которая принимается. Задача третьего судьи со сложностью 5 не выбирается. Жюри принимает решение выбрать еще 6 сложных задач, что в сумме дает сложность 54 + 6 · 50 = 354.

РЕШЕНИЕ

математика

Анализ алгоритма

Следует промоделировать процесс выбора задач, как описано в условии. Информацию о приготовленных задачах храним в списке списков (вектор векторов).

Реализация алгоритма

Пусть v[i] хранит сложности задач, подготовленных i-ым членом жюри.

vector<vector<int> > v;

Читаем входные данные. Вычисляем наибольшее количество задач mx, подготовленное одним членом жюри.

v.resize(n);

for (mx = i = 0; i < n; i++)

{

scanf("%d",&s);

mx = max(mx,s);

v[i].resize(s);

for (j = 0; j < s; j++)

scanf("%d",&v[i][j]);

}

В переменной sum подсчитываем общую сложность всех выбранных задач;

sum = 0;

Двигаемся по спискам – выбираем задачи на соревнование. Сначала проходим все нулевые позиции списков, потом первые, затем вторые и так далее. Переменная k содержит количество задач, которое еще следует выбрать на соревнование. Если будут выбраны все задачи (k станет равным 0), то выходим из циклов.

for(j = 0; (k > 0) && (j < mx); j++)

{

for (i = 0; (i < n) && (k > 0); i++)

{

i-ый член жюри предлагает свою j-ую задачу стоимостью cur.

cur = (j < v[i].size()) ? v[i][j] : 50;

if (cur >= sum)

{

sum += cur;

k--;

}

}

}

Соревнованию еще не хватает k задач (значение k может равняться и 0). Выбираем в качестве них сложные задачи со стоимостью 50.

sum += 50 * k;

Выводим общую сложность всех выбранных задач.

printf("%d\n", sum);